package com.wang.sort2;

/**
 * @Author: along
 * @Create: 2021/4/20
 * @Description:判断是否为满二叉树
 */
public class Demo17_IsFullBtree {
    public static class Node {
        public int val;
        public Node right;
        public Node left;

        public Node(int v) {
            this.val = v;
        }
    }
    public static class Info {
        public int height;
        public int nodes;

        public Info(int h, int n) {
            height = h;
            nodes = n;
        }
    }
    public static Info process(Node head) {
        if(head == null) {
            return new Info(0,0);
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int nodes = leftInfo.nodes + rightInfo.nodes + 1;
        return new Info(height,nodes);
    }
    public static boolean isFull(Node head) {
        if(head == null) {
            return true;
        }
        Info all = process(head);
        return all.nodes == (all.height << 1) - 1;//节点数等于树高的二次方减一即为满二叉树
    }
}
